{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Suffix Flips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minFlips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最少的后缀翻转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的二进制字符串 <code>target</code> 。你自己有另一个长度为 <code>n</code> 的二进制字符串 <code>s</code> ，最初每一位上都是 0 。你想要让 <code>s</code> 和 <code>target</code> 相等。</p>\n",
    "\n",
    "<p>在一步操作，你可以选择下标 <code>i</code>（<code>0 &lt;= i &lt; n</code>）并翻转在 <strong>闭区间</strong> <code>[i, n - 1]</code> 内的所有位。翻转意味着 <code>'0'</code> 变为 <code>'1'</code> ，而 <code>'1'</code> 变为 <code>'0'</code> 。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>返回使<em> </em><code>s</code><em> </em>与<em> </em><code>target</code> 相等需要的最少翻转次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"10111\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最初，s = \"00000\" 。\n",
    "选择下标 i = 2: \"00<em><strong>000</strong></em>\" -&gt; \"00<em><strong>111</strong></em>\"\n",
    "选择下标 i = 0: \"<em><strong>00111</strong></em>\" -&gt; \"<em><strong>11000</strong></em>\"\n",
    "选择下标 i = 1: \"1<em><strong>1000</strong></em>\" -&gt; \"1<em><strong>0111</strong></em>\"\n",
    "要达成目标，需要至少 3 次翻转。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"101\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最初，s = \"000\" 。\n",
    "选择下标 i = 0: \"<em><strong>000</strong></em>\" -&gt; \"<em><strong>111</strong></em>\"\n",
    "选择下标 i = 1: \"1<em><strong>11</strong></em>\" -&gt; \"1<em><strong>00</strong></em>\"\n",
    "选择下标 i = 2: \"10<em><strong>0</strong></em>\" -&gt; \"10<em><strong>1</strong></em>\"\n",
    "要达成目标，需要至少 3 次翻转。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"00000\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>由于 s 已经等于目标，所以不需要任何操作\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == target.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>target[i]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-suffix-flips](https://leetcode.cn/problems/minimum-suffix-flips/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-suffix-flips](https://leetcode.cn/problems/minimum-suffix-flips/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"10111\"', '\"101\"', '\"00000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        if target[-1] == '0':\n",
    "            res = 0\n",
    "        else:\n",
    "            res = 1\n",
    "        for i in range(len(target) - 2, -1, -1):\n",
    "            if target[i] == target[i + 1]:\n",
    "                continue\n",
    "            else:\n",
    "                if target[i] == '0':\n",
    "                    continue\n",
    "                else:\n",
    "                    res += 2\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flag,res=0,0\n",
    "        for t in target:\n",
    "            if t=='1' and flag==0:\n",
    "                res+=1\n",
    "                flag=1\n",
    "            elif t=='0' and flag==1:\n",
    "                res+=1\n",
    "                flag=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        count = 0\n",
    "        meet_1 = False\n",
    "\n",
    "        for i in range(len(target)):\n",
    "            if not meet_1 and target[i] == '1':\n",
    "                meet_1 = True\n",
    "                count += 1\n",
    "            if meet_1 and target[i] == '0':\n",
    "                count += 1\n",
    "                meet_1 = False\n",
    "\n",
    "        return count\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return target.count(\"01\")+target.count(\"10\")+int(target[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        front='0'\n",
    "        c=0\n",
    "        for i in target:\n",
    "            if i==front:\n",
    "                continue\n",
    "            else:\n",
    "                if i==1:\n",
    "                    front=i\n",
    "                    c+=1\n",
    "                else:\n",
    "                    front=i\n",
    "                    c+=1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n=len(target)\n",
    "        ans=0\n",
    "        flip=\"0\"\n",
    "        for i in range(n):\n",
    "            if target[i]!=flip:\n",
    "                ans+=1\n",
    "                flip=target[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips = 0\n",
    "        pre = \"0\"\n",
    "        for ch in target:\n",
    "            if ch != pre:\n",
    "                flips += 1\n",
    "            pre = ch\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        # 从0开始，每次变化都要加一\n",
    "        start = '0'\n",
    "        ans = 0\n",
    "        for c in target:\n",
    "            if c != start:\n",
    "                start = c\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n = len(target)\n",
    "        curr = '0'\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if target[i] != curr:\n",
    "                ret += 1\n",
    "                curr = target[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips, prev = 0, \"0\"\n",
    "        for curr in target:\n",
    "            if curr != prev:\n",
    "                flips += 1\n",
    "                prev = curr\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        # 怎么把target翻转成全部为0\n",
    "        res = 0\n",
    "        for i,c in enumerate(target):\n",
    "            if c=='1':\n",
    "                if res%2==0:\n",
    "                    res+=1\n",
    "            else:\n",
    "                if res%2==1:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return sum(x != y for x, y in pairwise('0' + target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return sum(1 for x, y in pairwise(target) if x != y) + (target[0] == '1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips, prev = 0, \"0\"\n",
    "        for curr in target:\n",
    "            if curr != prev:\n",
    "                flips += 1\n",
    "                prev = curr\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(target)\n",
    "        filp = 0\n",
    "        for i, x in enumerate(target):\n",
    "            x = int(x)\n",
    "            if filp == x: continue\n",
    "            else:\n",
    "                ans += 1\n",
    "                filp ^= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n = len(target)\n",
    "        ans = 0 if target[0] == '0' else 1\n",
    "        for i in range(1, n):\n",
    "            if target[i] != target[i - 1]:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        count, status = 0, 0\n",
    "        for c in target:\n",
    "            if int(c) != status:\n",
    "                count += 1\n",
    "                status = int(c)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        res = 0\n",
    "        pre = '0'\n",
    "        for c in target:\n",
    "            if pre != c:\n",
    "                res += 1\n",
    "                pre = c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        ans = 0\n",
    "        digit = 0\n",
    "        for i in range(len(target)):\n",
    "            if str(digit) != target[i]:\n",
    "                ans += 1\n",
    "                digit ^= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 贪心\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips, prev = 0, \"0\"\n",
    "        for curr in target:\n",
    "            if curr != prev:\n",
    "                flips += 1\n",
    "                prev = curr\n",
    "\n",
    "        return flips\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return sum(target[i] != target[i-1] for i in range(1, len(target))) + int(target[0]=='1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return sum(1 for x, y in pairwise(target) if x != y) + (target[0] == '1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n = 0\n",
    "        for i in range(len(target)):\n",
    "            if n % 2 == 1:\n",
    "                if target[i] == '0':\n",
    "                    n += 1\n",
    "            else:\n",
    "                if target[i] == '1':\n",
    "                    n += 1\n",
    "        return n\n",
    "#规律：连续相同的数字可视为一个，如：1001——>101,1110000111——>101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "\n",
    "        if target[0] != '0':\n",
    "            ans = 1\n",
    "        else:\n",
    "            ans = 0\n",
    "        n = len(target)\n",
    "        for i in range(1,n):\n",
    "            if target[i-1] != target[i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        ans = 0\n",
    "        prev = '0'\n",
    "        for c in target:\n",
    "            if c != prev:\n",
    "                ans += 1\n",
    "                prev = c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        #贪心地考虑\n",
    "        n=len(target)\n",
    "        ans=0 if target[0]==\"0\" else 1\n",
    "        for i in range(1,n):\n",
    "            if target[i]!=target[i-1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n=len(target)\n",
    "        ans=0 if target[0]==\"0\" else 1\n",
    "        for i in range(1,n):\n",
    "            if target[i]!=target[i-1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        cnt = 0\n",
    "        n = len(target)\n",
    "        later = '0'\n",
    "        for c in target:\n",
    "            #print(target[i], later)\n",
    "            if c != later:\n",
    "                if later == '1':\n",
    "                    later = '0'\n",
    "                else:\n",
    "                    later = '1'\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips = 0\n",
    "        pre = \"0\"\n",
    "        for ch in target:\n",
    "            if ch != pre:\n",
    "                flips += 1\n",
    "                pre = ch\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        if '1' not in target:\n",
    "            return 0\n",
    "        count = 0\n",
    "        i = 0\n",
    "        prev = None\n",
    "        while target[i] == '0':\n",
    "            i = i + 1\n",
    "        while i <= len(target) - 1:\n",
    "            cur = target[i]\n",
    "            if cur != prev:\n",
    "                count += 1\n",
    "                prev = cur\n",
    "            i = i + 1\n",
    "            print(count)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "\n",
    "\n",
    "        flips, prev = 0, \"0\"\n",
    "\n",
    "        for curr in target:\n",
    "            if curr != prev:\n",
    "                flips += 1\n",
    "                prev = curr\n",
    "\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "\n",
    "\n",
    "        flips, prev = 0, \"0\"\n",
    "\n",
    "        for curr in target:\n",
    "            if curr != prev:\n",
    "                flips += 1\n",
    "                prev = curr\n",
    "\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minFlips(self, target: str) -> int:\n",
    "    l = len(target)\n",
    "    ret, c, rv = 0, 0, target[-1]\n",
    "    for i in range(l - 2, -1, -1):\n",
    "      v = target[i]\n",
    "      if v != rv:\n",
    "        ret += 1\n",
    "        rv = v\n",
    "    return ret if '0' == rv else ret + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return sum(x != y for x, y in pairwise('0' + target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(target)):\n",
    "            if target[i] != target[i-1]:\n",
    "                ans += 1\n",
    "        if target[0] == '1':\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        prev = target[0]\n",
    "        ans = 1 if prev == \"1\" else 0\n",
    "        for num in target[1:]:\n",
    "            if num != prev:\n",
    "                ans += 1\n",
    "                prev = num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        ans = 0\n",
    "        s = '01'\n",
    "        flag = 0\n",
    "        for i in range(len(target)):\n",
    "            if s[flag] != target[i]:\n",
    "                ans += 1\n",
    "                flag ^= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        cnt = int(target[0])\n",
    "        for i in range(1, len(target)):\n",
    "            if target[i] != target[i - 1]:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n=len(target)\n",
    "        ans=0\n",
    "        flip=\"0\"\n",
    "        for i in range(n):\n",
    "            if target[i]!=flip:\n",
    "                ans+=1\n",
    "                flip=target[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "\n",
    "        if target[0] != '0':\n",
    "            ans = 1\n",
    "        else:\n",
    "            ans = 0\n",
    "        n = len(target)\n",
    "        for i in range(1,n):\n",
    "            if target[i-1] != target[i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips, prev = 0, \"0\"\n",
    "        for char in target:\n",
    "            if char != prev:\n",
    "                flips += 1\n",
    "                prev = char\n",
    "        return flips"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target):\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        if target == None or len(target) == 0:\n",
    "            return 0 \n",
    "        \n",
    "        n = len(target)\n",
    "        first_one_pos = 0\n",
    "        #去除掉target的前缀0, 找到第一个1出现的位置\n",
    "        for i in range(n):\n",
    "            if target[i] == '1':\n",
    "                first_one_pos = i \n",
    "                break \n",
    "\n",
    "        #为了便于后序计算, 将target视作二进制数\n",
    "        target_num = 0 \n",
    "        product = 1 \n",
    "\n",
    "        for i in range(n - 1, first_one_pos - 1, -1):\n",
    "            cur_num = ord(target[i]) - ord('0')\n",
    "            target_num += cur_num * product\n",
    "            product *= 2 \n",
    "        \n",
    "        # print(target_num)\n",
    "\n",
    "        s_num = 0\n",
    "        ans = 0\n",
    "        n = n - first_one_pos\n",
    "\n",
    "        #使用贪心算法, 从头开始, 每当cur_s于target在idx处不一致, 就进行一次翻转\n",
    "        for i in range(n):\n",
    "            flag = (s_num ^ target_num) & (1 << (n - i - 1))    #查看在i位置上两数是否一致\n",
    "            if flag:\n",
    "                ans += 1\n",
    "                s_num = self.convert(s_num, i, n)\n",
    "                \n",
    "        return ans  \n",
    "\n",
    "    def convert(self, cur_num, index, n):\n",
    "        \"\"\"\n",
    "        将cur_num二进制中的[index...]后几位都进行翻转\n",
    "        Args:\n",
    "            cur_num (int): 当前数\n",
    "            index (int): 开始翻转的索引\n",
    "            n (int):    原始字符串的长度\n",
    "        returns (int): 翻转后的数\n",
    "        \"\"\"\n",
    "        length = n - index \n",
    "        #得到后length都是1的二进制数\n",
    "        other = (1 << length) - 1\n",
    "\n",
    "        return cur_num ^ other \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        return sum(1 for x, y in pairwise(target) if x != y) + (target[0] == '1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        cnt = 0\n",
    "        n = len(target)\n",
    "        later = '0'\n",
    "        for i in range(n):\n",
    "            #print(target[i], later)\n",
    "            if target[i] == later:\n",
    "                continue\n",
    "            if target[i] != later:\n",
    "                if later == '1':\n",
    "                    later = '0'\n",
    "                else:\n",
    "                    later = '1'\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        # 怎么把target翻转成全部为0\n",
    "        # 从左至右遍历，记录翻转次数。翻转次数为偶数，那么翻转结果不会变。\n",
    "        # 为奇数，那么0和1会翻转，因为我们是要把全部1变成0，所以当前翻转后是1时，\n",
    "        # 就需要增加一次翻转次数\n",
    "        res = 0\n",
    "        for i,c in enumerate(target):\n",
    "            if c=='1':\n",
    "                if res%2==0:\n",
    "                    res+=1\n",
    "            else:\n",
    "                if res%2==1:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        flips = 0\n",
    "        tmp = '0'\n",
    "\n",
    "        for num in target:\n",
    "            if num != tmp:\n",
    "                flips += 1\n",
    "                tmp = num\n",
    "        return flips "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, target: str) -> int:\n",
    "        n=len(target)\n",
    "        ans=0 if target[0]==\"0\" else 1\n",
    "        for i in range(1,n):\n",
    "            if target[i]!=target[i-1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
